#include "bitmap.h"
#include "stdint.h"
#include "string.h"
#include "print.h"
#include "interrupt.h"
#include "debug.h"

// 初始化位图 btmp
void bitmap_init(struct bitmap* btmp) {
    memset(btmp -> bits, 0, btmp -> btmp_bytes_len);
}

// 判断第 bit_idx 位是否为 1，若为 1，则返回 true，反之 false
bool bitmap_scan_test(struct bitmap* btmp, uint32_t bit_idx) {
    uint32_t byte_idx = bit_idx / 8; // 向下取整，得到 bit_idx 所在字节，即数组下标索引
    uint32_t bit_odd = bit_idx % 8; // 取余，表示字节中的位
    return (btmp -> bits[byte_idx] & (BITMAP_MASK << bit_odd));
}

// 在位图中申请连续 cnt 个位，返回起始下标，否则返回 -1
// 例如：bits[0] = 00000000, bits[1] = 00000010, bits[i] ...
// 返回 bits[1] 中的 1 下标为：1*8+6=14
int bitmap_scan(struct bitmap* btmp, uint32_t cnt) {
    uint32_t idx_byte = 0; // 记录空闲位所在字节
    // 先逐字比较
    while((btmp->bits[idx_byte] == 0xFF) && (idx_byte < btmp->btmp_bytes_len)) idx_byte++;
    ASSERT(idx_byte < btmp->btmp_bytes_len);
    if(idx_byte == btmp->btmp_bytes_len) return -1; // 无可用空间

    // 若在位图某字节中有空闲位，则在该字节上进行逐位比对
    int idx_bit = 0; // 记录空闲位的索引
    while((uint8_t)(BITMAP_MASK << idx_bit) & btmp -> bits[idx_byte]) idx_bit++;

    int bit_idx_start = idx_byte * 8 + idx_bit; // 空闲位在位图中的下标
    if(cnt == 1) return bit_idx_start;

    uint32_t bit_left = (btmp -> btmp_bytes_len * 8 - bit_idx_start); // 记录还有多少位可以判断
    uint32_t next_bit = bit_idx_start + 1; // 下一个位的下标
    uint32_t count = 1; // 记录找到了多少个空闲位

    bit_idx_start = -1; // 在 bit_idx_start == cnt 之前先置为 -1
    while(bit_left-- > 0) {
        if(!(bitmap_scan_test(btmp, next_bit))) count++; // next_bit 未使用
        else count = 0; // next_bit 被使用，导致不连续，因此之前的全部废除，重新从 0 开始计算
        if(count == cnt) { // 找到了连续的 cnt 个空闲位
            bit_idx_start = next_bit - cnt + 1;
            break;
        }
        next_bit++;
    }

    return bit_idx_start;
}

// 将位图 btmp 的第 bit_idx 个位设置位 value(0 or 1)
void bitmap_set(struct bitmap* btmp, uint32_t bit_idx, int8_t value) {
    ASSERT((value == 0) || (value == 1));
    uint32_t byte_idx = bit_idx / 8; // 找到 bit_idx 所在字节
    uint32_t bit_odd = bit_idx % 8;  // 找到字节内的位
    if(value) btmp -> bits[byte_idx] |= (BITMAP_MASK << bit_odd); // value = 1
    else btmp -> bits[byte_idx] &= ~(BITMAP_MASK << bit_odd); // value = 0
}

